#pragma once


#include<iostream>
#include<cassert>

using namespace std;

namespace bit
{
	enum color
	{
		BLACK,
		RED,
	};

	template<class v >
	struct RBTNode
	{
		v _kv;
		RBTNode<v>* _left;
		RBTNode<v>* _right;
		RBTNode<v>* _parent;
		color _col;


		RBTNode(const v& key)
			:_kv(key)
			, _left(nullptr)
			, _right(nullptr)
			, _parent(nullptr)
			, _col(RED)
		{}
	};

	template<class v, class ref, class ptr>
	struct RBTreeIterator
	{
		typedef RBTNode<v> Node;
		typedef RBTreeIterator<v, ref, ptr> self;

		RBTreeIterator(Node* node, Node* root)
			:_node(node)
			, _root(root)
		{}

		bool operator!= (const self& key)
		{
			return _node != key._node;
		}

		bool operator==(const self& key)
		{
			return _node == key._node;
		}

		ref operator*()
		{
			return _node->_kv;
		}

		ptr operator->()
		{
			return &_node->_kv;
		}

		self& operator++()
		{
			if (_node && _node->_right)
			{
				Node* right = _node->_right;
				while (right->_left)
				{
					right = right->_left;
				}
				_node = right;
			}
			else if (_node && _node->_right == nullptr)
			{
				Node* parent = _node->_parent;
				while (parent != nullptr && _node == parent->_right)
				{
					_node = parent;
					parent = _node->_parent;
				}
				_node = parent;
			}
			return *this;
		}


		self& operator--()
		{
			if (_node == nullptr)
			{
				Node* right = _root;
				while (right && right->_right)
				{
					right = right->_right;
				}
				_node = right;
			}
			else if (_node->_left)
			{
				Node* left = _node->_left;
				while (left->_right)
				{
					left = left->_right;
				}
				_node = left;
			}
			else
			{
				Node* parent = _node->_parent;
				while (parent != nullptr && _node == parent->_left)
				{
					_node = parent;
					parent = _node->_parent;
				}
				_node = parent;
			}
			return *this;
		}

		Node* _root;
		Node* _node;
	};

	template<class k, class v, class KeyofT>
	class RBTree
	{
		typedef RBTNode<v> Node;
	public:
		typedef RBTreeIterator<v, v&, v*> iterator;
		typedef RBTreeIterator<v, v&, const v*> Constiterator;
		RBTree() = default;
		RBTree(const RBTree& root)
		{
			_root = Copy(root._root);
		}

		~RBTree()
		{
			Destroy(_root);
			_root = nullptr;
		}

		iterator begin()
		{
			Node* root = _root;
			while (root && root->_left)
			{
				root = root->_left;
			}
			return iterator(root, _root);
		}

		Constiterator begin() const
		{
			Node* root = _root;
			while (root && root->_left)
			{
				root = root->_left;
			}
			return Constiterator(root, _root);
		}


		iterator end()
		{
			return iterator(nullptr, _root);
		}


		Constiterator end() const
		{
			return Constiterator(nullptr, _root);
		}

		bool empty()
		{
			return _root == nullptr;
		}

		pair<iterator, bool> Insert(v& ret)
		{
			if (_root == nullptr)
			{
				_root = new Node(ret);
				_root->_col = BLACK;
				return make_pair(iterator(_root, _root), true);
			}
			Node* prev = nullptr;
			Node* root = _root;
			KeyofT key;
			while (root != nullptr)
			{
				if (key(root->_kv) > key(ret))
				{
					prev = root;
					root = root->_left;
				}
				else if (key(root->_kv) < key(ret))
				{
					prev = root;
					root = root->_right;
				}
				else return make_pair(iterator(root, _root), false);
			}
			Node* cur = new Node(ret);
			Node* Curnode = cur;
			if (key(prev->_kv) > key(ret))
			{
				prev->_left = cur;
				cur->_parent = prev;
			}
			else
			{
				prev->_right = cur;
				cur->_parent = prev;
			}

			while (prev && prev->_col == RED)
			{
				Node* grandfather = prev->_parent;
				Node* uncle = nullptr;
				if (grandfather->_left == prev)
				{
					uncle = grandfather->_right;
				}
				else
				{
					uncle = grandfather->_left;
				}

				if (uncle && uncle->_col == RED)
				{
					prev->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					prev = cur->_parent;
				}
				else if (uncle == nullptr || uncle->_col == BLACK)
				{
					if (cur == prev->_left && grandfather->_left == prev)
					{
						RotetaR(grandfather);
						grandfather->_col = RED;
						prev->_col = BLACK;
					}
					else if (cur == prev->_right && grandfather->_right == prev)
					{
						RotetaL(grandfather);
						grandfather->_col = RED;
						prev->_col = BLACK;
					}
					else if (grandfather->_left == prev && prev->_right == cur)
					{
						RotetaL(prev);
						RotetaR(grandfather);
						grandfather->_col = RED;
						cur->_col = BLACK;
					}
					else if (grandfather->_right == prev && prev->_left == cur)
					{
						RotetaR(prev);
						RotetaL(grandfather);
						grandfather->_col = RED;
						cur->_col = BLACK;
					}
					break;
				}
			}

			_root->_col = BLACK;


			return make_pair(iterator(Curnode, _root), true);
		}

		iterator Find(const k& ret)
		{
			Node* root = _root;
			KeyofT key;
			while (root != nullptr)
			{
				if (key(root->_kv) > ret)
				{
					root = root->_left;
				}
				else if (key(root->_kv) < ret)
				{
					root = root->_right;
				}
				else return iterator(root, _root);
			}
			return end();
		}

		void Inorder()
		{
			inorder(_root);
			cout << endl;
		}



	private:



		void RotetaL(Node* prev)
		{
			Node* right = prev->_right;
			Node* parent = prev->_parent;

			prev->_right = right->_left;
			if (right->_left)
			{
				right->_left->_parent = prev;
			}

			right->_left = prev;
			prev->_parent = right;

			if (parent == nullptr)
			{
				_root = right;
			}
			else
			{
				if (parent->_left == prev)
				{
					parent->_left = right;
				}
				else
				{
					parent->_right = right;
				}

			}
			right->_parent = parent;
		}

		void RotetaR(Node* prev)
		{
			Node* left = prev->_left;
			Node* parent = prev->_parent;

			prev->_left = left->_right;
			if (left->_right)
			{
				left->_right->_parent = prev;
			}

			left->_right = prev;
			prev->_parent = left;

			if (parent == nullptr)
			{
				_root = left;
			}
			else
			{
				if (parent->_left == prev)
				{
					parent->_left = left;
				}
				else
				{
					parent->_right = left;
				}
			}
			left->_parent = parent;

		}

		void inorder(Node* root)
		{
			if (root == nullptr) return;

			inorder(root->_left);
			cout << root->_kv.first << ' ';
			inorder(root->_right);
		}

		Node* Copy(const Node* root)
		{
			if (root == nullptr) return nullptr;

			Node* val = new Node(root->_kv);
			val->_left = Copy(root->_left);
			val->_right = Copy(root->_right);
			return val;
		}

		void Destroy(Node* root)
		{
			if (root == nullptr) return;

			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
		}

		Node* _root = nullptr;
	};
}
